Thực đơn
Giải_thuật_Euclid_mở_rộng Cơ sở lý thuyết của giải thuậtGiải thuật Eclid mở rộng kết hợp quá trình tìm ƯCLN(a, b) trong thuật toán Eclid với việc tìm một cặp số x, y thoả mãn phương trình Đi-ô-phăng.Giả sử cho hai số tự nhiên a, b, ngoài ra a>b>0.Đặt r o = a , r 1 = b {\displaystyle r_{o}=a,r_{1}=b} , chia r 0 {\displaystyle r_{0}} cho r 1 {\displaystyle r_{1}} được số dư r 2 {\displaystyle r_{2}} và thương số nguyên q 1 {\displaystyle q_{1}} . Nếu r 2 = 0 {\displaystyle r_{2}=0} thì dừng,nếu r 2 {\displaystyle r_{2}} khác không, chia r 1 {\displaystyle r_{1}} cho r 2 {\displaystyle r_{2}} được số dư r 3 {\displaystyle r_{3}} ,...Vì dãy các r i {\displaystyle r_{i}} là giảm thực sự nên sau hữu hạn bước ta được số dư r m + 2 = 0 {\displaystyle r_{m+2}=0} .
trong đó số dư cuối cùng khác 0 là r m + 1 = d {\displaystyle r_{m+1}=d} .Bài toán đặt ra là tìm x, y sao cho
a ∗ x + b ∗ y = r m + 1 ( = d ) {\displaystyle a*x+b*y=r_{m+1}(=d)}Để làm điều này, ta tìm x, y theo công thức truy hồi, nghĩa là sẽ tìm
x i {\displaystyle x_{i}} và y i {\displaystyle y_{i}} sao cho: a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .Ta có
a ∗ 1 + b ∗ 0 = a = r o {\displaystyle a*1+b*0=a=r_{o}} và a ∗ 0 + b ∗ 1 = b = r 1 {\displaystyle a*0+b*1=b=r_{1}} , nghĩa là x o = 1 , x 1 = 0 {\displaystyle x_{o}=1,x_{1}=0} và y o = 0 , y 1 = 1 {\displaystyle y_{o}=0,y_{1}=1} . (1)Tổng quát, giả sử có
a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} . a ∗ x i + 1 + b ∗ y i + 1 = r i + 1 {\displaystyle a*x_{i+1}+b*y_{i+1}=r_{i+1}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .Khi đó từ
r i = q i + 1 ∗ r i + 1 + r i + 2 {\displaystyle r_{i}=q_{i+1}*r_{i+1}+r_{i+2}}suy ra
r i − q i + 1 ∗ r i + 1 = r i + 2 {\displaystyle r_{i}-q_{i+1}*r_{i+1}=r_{i+2}} ( a ∗ x i + b ∗ y i ) − q i + 1 ∗ ( a ∗ x i + 1 + b ∗ y i + 1 ) = r i + 2 {\displaystyle (a*x_{i}+b*y_{i})-q_{i+1}*(a*x_{i+1}+b*y_{i+1})=r_{i+2}} a ∗ ( x i − q i + 1 ∗ x i + 1 ) + b ∗ ( y i − q i + 1 ∗ y i + 1 ) = r i + 2 {\displaystyle a*(x_{i}-q_{i+1}*x_{i+1})+b*(y_{i}-q_{i+1}*y_{i+1})=r_{i+2}}từ đó, có thể chọn
Khi i = m − 1 {\displaystyle i=m-1} ta có được x m + 1 {\displaystyle x_{m+1}} và y m + 1 {\displaystyle y_{m+1}} .Các công thức (1), (2), (3) là công thức truy hồi để tính x, y.
{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}function gcd(a, b);begin while b ≠ 0 do begin r:= a mod b; a:= b; b:= r; end; Result:= a;end;{Thuật toán Euclide mở rộng: a, b không đồng thời bằng 0, trả về cặp (x, y) sao cho a * x + b * y = gcd(a, b)Về tư tưởng là ghép quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclide.}function Extended_gcd(a, b); begin (xa, ya):= (1, 0); (xb, yb):= (0, 1); while b ≠ 0 do begin q:= a div b; r:= a mod b; a:= b; b:= r; //Đoạn này giống thuật toán Euclide. (xr, yr):= (xa, ya) - q * (xb, yb); //Hiểu là: (xr, yr):= (xa, ya) "mod" (xb, yb); (xa, ya):= (xb, yb); (xb, yb):= (xr, yr); end; Result:= (xa, ya);end;
Giải thuật sau chỉ thực hiện với các số nguyên a>b>0, biểu diễn bằng giải mã:
Sub Euclid_Extended(a,b) Dim x0, x, y,y1 As Single x0=1: x1=0: y0=0: y1=1 While b>0 r= a mod b if r=0 then Exit While q= a / b x= x0-x1*q y= y0-y1*q a=b b=r x0=x1 x1=x y0=y1 y1=y Wend Me.Print d:=b, x, ycode End Sub
Với a=29, b=8, giải thuật trải qua các bước như sau
Bước i {\displaystyle i} | r i {\displaystyle r_{i}} | r i + 1 {\displaystyle r_{i+1}} | r i + 2 {\displaystyle r_{i+2}} | q i + 1 {\displaystyle q_{i+1}} | x i {\displaystyle x_{i}} | x i + 1 {\displaystyle x_{i+1}} | x i + 2 {\displaystyle x_{i+2}} | y i {\displaystyle y_{i}} | y i + 1 {\displaystyle y_{i+1}} | y i + 2 {\displaystyle y_{i+2}} |
0 | 29 | 8 | 5 | 3 | 1 | 0 | 1 | 0 | 1 | -3 |
1 | 8 | 5 | 3 | 1 | 0 | 1 | -1 | 1 | -3 | 4 |
2 | 5 | 3 | 2 | 1 | 1 | -1 | 2 | -3 | 4 | -7 |
3 | 3 | 2 | 1 | 1 | -1 | 2 | -3 | 4 | -7 | 11 |
4 | 2 | 1 | 0 | 2 |
Kết quả thuật toán cho đồng thời d = U C L N ( 29 , 8 ) = 1 {\displaystyle d=UCLN(29,8)=1} và x = − 3 {\displaystyle x=-3} , y = 11 {\displaystyle y=11} .
Dễ dàng kiểm tra hệ thức 29 ∗ ( − 3 ) + 8 ∗ 11 = 1 {\displaystyle 29*(-3)+8*11=1}
Thực đơn
Giải_thuật_Euclid_mở_rộng Cơ sở lý thuyết của giải thuậtLiên quan
Giải Giải bóng đá Ngoại hạng Anh Giải vô địch bóng đá U-23 châu Á 2018 Giải vô địch bóng đá châu Âu 2012 Giải vô địch bóng đá châu Âu 2024 Giải bóng đá vô địch quốc gia Đức Giải bóng rổ Nhà nghề Mỹ Giải vô địch bóng đá U-23 châu Á 2020 Giải vô địch bóng đá thế giới Giải bóng đá Vô địch Quốc gia Việt NamTài liệu tham khảo
WikiPedia: Giải_thuật_Euclid_mở_rộng http://banach.millersville.edu/~bob/math478/Extend... http://marauder.millersville.edu/~bikenaga/absalg/... http://student.mst.edu.hk/~s0210043/mulinv.cpp http://mathforum.org/library/drmath/view/51675.htm... http://homepages.inf.ed.ac.uk/s0563270/maths/javas... http://homepages.inf.ed.ac.uk/s0563270/maths/php/e...